/*
 * File:   main.cpp
 * Author: Toya
 *
 * Created on 4 octobre 2012, 19:59
 */

#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <math.h>
#include <list>
#include <algorithm>
using namespace std;


int n; // nb sommets
int m;//nb aretes
vector<vector<vector<int> > > G;
vector<vector<vector<int> > > Gp;
//vector<vector<int> >  chemin;
vector<vector<vector<int> > > Gc;
int** ind;
int** indgp;
vector< vector<int> > aretes;

 struct MonFoncteur
{
   bool operator() (const vector<int> & lhs, const vector<int> & rhs) const
   {
      return lhs[2] < rhs[2];
   }
};  

void ajouteArete(int a,int b,int f, int c){


//pas d'arc croisés
for(int i=0; i<G[b].size();i++){
        if(G[b][i][0]==a) {
            G[b][i] =  G[b].back();
            //ind[b][G[b][G[b].size()-1][0]]=-1;
                            G[b].pop_back();m--;
                            }
        }

//pas d'arc doubles/triples...
for(int i=0; i<G[a].size();i++){
        if(G[a][i][0]==b) {
                            G[a][i] =  G[a].back();
                          //  ind[a][G[a][G[a].size()-1][0]]=-1;
                            G[a].pop_back();m--;
                            }
        }

     G[a].push_back(vector<int>());
        G[a][G[a].size()-1].push_back(b);
        G[a][G[a].size()-1].push_back(f);
        G[a][G[a].size()-1].push_back(c);
        ind[a][b]=G[a].size()-1;
        m++;


}
void ajouteAreteGp(int a,int b,int f, int c){

     Gp[a].push_back(vector<int>());
        Gp[a][Gp[a].size()-1].push_back(b);
        Gp[a][Gp[a].size()-1].push_back(f);
        Gp[a][Gp[a].size()-1].push_back(c);
        indgp[a][b]=Gp[a].size()-1;

}


void initGraphe(){
   string s = "";
    cout<<"Combien de sommets ?"<<endl<<">";
    cin>>n;
    ind = new int*[n];

  for (int i = 0 ; i < n ; i++)
      ind[i] = new int[n];

    indgp = new int*[n];

  for (int i = 0 ; i < n ; i++)
      indgp[i] = new int[n];

    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            ind[i][j]=-1;
            indgp[i][j]=-1;
        }

    }

    for(int i=0;i<n;i++){
        G.push_back(vector<vector<int> >());
    }

    cout<<"indiquez vos aretes et finissez par 'fin'"<<endl;
     cout<<"i j flot capacit�"<<endl;

        cout<<">";
     getline (cin,s);
    getline (cin,s);
    s+=" ";

    int cpt=0;
    int c=0;
    string str="";
    while(s!="fin "){
         cpt=0;
         c=0;
         str="";
         int t[4];
        while(cpt<4 ){
           if(s[c]!=' '){
               str+=s[c];
               c++;
           }
           else{

               istringstream iss(str);
               iss >> t[cpt];
               cpt++;
               str="";
               c++;
           }


        }

        G[t[0]].push_back(vector<int>());
        G[t[0]][G[t[0]].size()-1].push_back(t[1]);
        G[t[0]][G[t[0]].size()-1].push_back(t[2]);
        G[t[0]][G[t[0]].size()-1].push_back(t[3]);
        ind[t[0]][t[1]]=G[t[0]].size()-1;
      //  a=atoi(s[0]);
      cout<<">";
           getline (cin,s);
            s+=" ";
    }

}

/**
cr�e dans Gp le graphe d'�cart de G

**/
void graphEcart(){



for(int i=0;i<n;i++){
        Gp.push_back(vector<vector<int> >());
    }



                 for(int i=0;i<n;i++){

                        for(int j=0;j<G[i].size();j++){



                                     //on rajoute un arc arri�re dont le flot �gal �valeur du flot ij et capacit� pareil
                                if(G[i][j][1] != 0 ){
                                    //  cout<<" TRace 2 :"<<G[i][j][0]<<"  : "<<Gp[G[i][j][0]].size()<<endl;

                                        Gp[G[i][j][0]].push_back(vector<int>());

                                   // cout<<" TRace 2.1"<<endl;
                                 Gp[G[i][j][0]][Gp[G[i][j][0]].size()-1].push_back(i);
                                 Gp[G[i][j][0]][Gp[G[i][j][0]].size()-1].push_back(G[i][j][1]);
                                 Gp[G[i][j][0]][Gp[G[i][j][0]].size()-1].push_back(G[i][j][1]);

                                 indgp[G[i][j][0]][i]=Gp[G[i][j][0]].size()-1;
                                }


                                     //le flot des arc avant �gual � la difference capacit� flot
                                     if((G[i][j][2] -G[i][j][1]) != 0 ){

                                      //   if((Gp[i].size()-1)<j)
                                         Gp[i].push_back(vector<int>());

                                Gp[i][Gp[i].size()-1].push_back(G[i][j][0]);
                                Gp[i][Gp[i].size()-1].push_back(G[i][j][2] -G[i][j][1]);
                                Gp[i][Gp[i].size()-1].push_back(G[i][j][2] -G[i][j][1]);

                                indgp[i][G[i][j][0]]= Gp[i].size()-1;
                        }}





                 }}




vector <int> pcChemin(int s, int t){

    int cpt=0;
    bool vu[n];
    int pere[n]/*[2]*/;
    bool trouve=false;
    for( int i=0;i<n;i++){
        vu[i]=false;
        pere[i]/*[0]*/=-1;
    }
    vector<int> aTraiter;


    aTraiter.push_back(s);

    int j=0;
    int i=0;
    int k=0;
    while(!trouve){//le chemin max est de taille n dans le pire des cas

        //pour les nouveaux voisins, on regarde si c'est t sinon
        if(aTraiter.size()==j)trouve=true;
            else{ j=aTraiter.size();
                while(i<j){

                             //on parcours les nouveaux voisins du sommet courant et on met le sommet courant comme pere
                             //for(int k=0;k<Gp[aTraiter[i]].size();k++){
                    k=0;
                              while(k<Gp[aTraiter[i]].size())  {
                             if(!vu[Gp[aTraiter[i]][k][0]]){
                                   if(Gp[aTraiter[i]][k][0]==t){//c'est gagn�

                                   trouve=true;
                                   pere[t]/*[0]*/=aTraiter[i];
                                  // pere[t][1]=k;//G[aTraiter[i]][k][2]-G[aTraiter[i]][k][1];
                                   k=Gp[aTraiter[i]].size();
                                   }
                                   else{
                                       vu[Gp[aTraiter[i]][k][0]]=true;
                                       pere[Gp[aTraiter[i]][k][0]]/*[0]*/=aTraiter[i];
                                      // pere[Gp[aTraiter[i]][k][0]][1]=k;//G[aTraiter[i]][k][2]-G[aTraiter[i]][k][1];
                                       aTraiter.push_back(Gp[aTraiter[i]][k][0]);
                                   }
                                 }
                            k++; }

              i++;
            }

        }

       cpt++;
    }

    vector <int> chemin;

    if(pere[t]/*[0]*/!=-1){

    chemin.resize(cpt+1,-1);

        chemin[cpt]=t;

    for(int l=cpt;l>0;l--){

       chemin[l-1]=pere[chemin[l]]/*[0]*/;

    }
    }
    else{

        chemin.push_back(-1);
    }
  return chemin;
}

void afficheGraphe(vector<vector<vector<int> > > g){

    for(int i=0;i<n;i++){

        cout<<i<<" relie a : ";

        for(int j=0;j<g[i].size();j++){

             cout<<g[i][j][0]<<" ("<<g[i][j][1]<<"/"<<g[i][j][2]<<") , ";

        }
    cout<<endl;
     }

}

int random(int a,int b){//retourne un nb alea de a à b avec a>=0 et b>a

    return (a + (int)((double)rand() / ((double)RAND_MAX + 1) * b));



}


/** retourne vrai si ya au moins un arc sortant et entrant au sommet i

nb = 1 : que sortant, 2 que entrant , 3 les deux

**/
bool sortantEtEntrant(int i,int nb){

if(nb==3)
{
    //sortant
    if(G[i].size()==0)
    return false;

    //entrant
    for(int j=0;j<G.size();j++)
    {
        for(int k=0;k<G[j].size();k++)
                {
                    if(G[j][k][0]==i)
                    return true;
                }

    }


    return false;

}

if(nb==1)
{
//sortant
    if(G[i].size()==0)
    return false;

    return true;

}

if(nb==2)
{
 //entrant
    for(int j=0;j<G.size();j++)
    {
        for(int k=0;k<G[j].size();k++)
                {
                    if(G[j][k][0]==i)
                    return true;
                }

    }


    return false;

}

}

void initGrapheRandom(int capMax,int P_avant, int P_arriere){//P_avant=proba d'avoir un arc avant en %, P_arriere=proba d'avoir un arc arriere en %, le reste c'est pas d'arrete


   /* cout<<"Combien de sommets ?"<<endl<<">";
    cin>>n;*/


     ind = new int*[n];
     bool premiereFois=true;
  for (int i = 0 ; i < n ; i++)
      ind[i] = new int[n];

    indgp = new int*[n];

  for (int i = 0 ; i < n ; i++)
      indgp[i] = new int[n];



     for(int i=0;i<n;i++){
        G.push_back(vector<vector<int> >());
    }



    srand(time(NULL));
    P_arriere+=P_avant;
    // P_arriere 90 et P_avant 20

    int r=0;
    int r2=0;

            while(premiereFois){
          for(int j=1;j<n-1;j++){//pour la source
            r=random(0,100);
                if(r<P_avant){
                     r2=random(1,capMax);
                    ajouteArete(0,j,0,r2);
                }
            }
          premiereFois=!sortantEtEntrant(0,1);
            }
premiereFois=true;
while(premiereFois){
        //pour le puit
        r=random(0,100);
         if(r<P_avant){
        r2=random(1,capMax);
    ajouteArete(0,n-1,0,r2);
         }
        premiereFois=!sortantEtEntrant(n-1,2);
}

    for(int i=1;i<n-1;i++){
        premiereFois=true;
        while(premiereFois ){ // pour chaque sommet on continu les random tant que ya pas rajouté au moins un entrant et un sortant

        for(int j=1;j<n-1;j++){
            if(i!=j){
            r=random(0,100);
            if(r<P_arriere){
                r2=random(1,capMax);
                if(r<P_avant){ // rajout arrete sortante
                     ajouteArete(i,j,0,r2);
                }else{  // rajout arrete entrante
                    ajouteArete(j,i,0,r2);
                }
            }
            }
        }



       //pour le puit
        r=random(0,100);
         if(r<P_avant){ // rajout arrete sortante vers le puit
        r2=random(1,capMax);

          ajouteArete(i,n-1,0,r2);
         }
premiereFois=!sortantEtEntrant(i,3);
    }
    }

    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            ind[i][j]=-1;
            indgp[i][j]=-1;
        }

    }
for(int i=0;i<n;i++){
    for(int j=0;j<G[i].size();j++){
        ind[i][G[i][j][0]]=j;
 
    }
   
}

}



int indiceArete(int a,int b){

   /* int i=0;

        while(i<Gp[a].size()){
         if(Gp[a][i][0]==b)break;
         else i++;
    }
    return i;*/
    return ind[a][b];
}
int indiceAreteGp(int a,int b){
       return indgp[a][b];

}

/*int* plusPetitArc(vector < int > chemin){

    int min=INT_MAX;
    int imin=-1;
    int j=-1;
    for(int i=0;i<chemin.size()-1;i++){
        j=indiceArete(chemin[i],chemin[i+1]);

       if((G[chemin[i]][j][2]-G[chemin[i]][j][1])<min){
            imin=i;min=G[chemin[i]][j][2]-G[chemin[i]][j][1];
        }
    }
    int *t=new int[3];t[0]=chemin[imin];t[1]=chemin[imin+1];t[2]=min;
    return t;
}*/

int* plusPetitArc(vector < int > chemin){

    int min=INT_MAX;
    int imin=-1;
    int tp=-1;
    for(int i=1;i<chemin.size();i++){

       // tp=G[chemin[i-1]][pere[chemin[i]][1]][2]-G[chemin[i-1]][pere[chemin[i]][1]][1];
        tp=Gp[chemin[i-1]][indiceAreteGp(chemin[i-1],chemin[i])][1];
       if(tp<min){
            imin=i-1;min=tp;
        }
    }
    int *t=new int[3];t[0]=chemin[imin];t[1]=chemin[imin+1];t[2]=min;
    return t;
}

void MaJGp(vector<int> chemin,int f){
    int j=-1;
    int k=-1;

    for(int i=0;i<chemin.size()-1;i++){
       j= indiceAreteGp(chemin[i],chemin[i+1]);
       Gp[chemin[i]][j][1]-=f;//on enleve le flot du plus petit arc a chaque arete du chemin

       k= indiceAreteGp(chemin[i+1],chemin[i]);//ca c'est pour l'arete inverse

         if(k!=-1/*Gp[chemin[i+1]].size()*/){
           Gp[chemin[i+1]][k][1]+=f;

         }
         else{
           ajouteAreteGp(chemin[i+1],chemin[i],f, Gp[chemin[i]][j][2]);

         }

       if(Gp[chemin[i]][j][1]==0){// si le flot fait 0 sur l'arete
           if(j!=Gp[chemin[i]].size()-1){
               indgp[chemin[i]][Gp[chemin[i]][j][0]]=-1;
               Gp[chemin[i]][j][0]=Gp[chemin[i]][Gp[chemin[i]].size()-1][0];
               Gp[chemin[i]][j][1]=Gp[chemin[i]][Gp[chemin[i]].size()-1][1];
               Gp[chemin[i]][j][2]=Gp[chemin[i]][Gp[chemin[i]].size()-1][2];
               indgp[chemin[i]][Gp[chemin[i]][j][0]]=j;
               Gp[chemin[i]][Gp[chemin[i]].size()-1].clear();
               Gp[chemin[i]].pop_back();
           }
           else{
               indgp[chemin[i]][Gp[chemin[i]][j][0]]=-1;
               Gp[chemin[i]][Gp[chemin[i]].size()-1].clear();
               Gp[chemin[i]].pop_back();
           }
       }
   }

}

int GpFinal(){
    vector<int> chemin;
    int *t;
    int flot=0;
    chemin=pcChemin(0,n-1);
    int cpt=0;
    while(chemin[0]!=-1){

        t=plusPetitArc(chemin);

         MaJGp(chemin,t[2]);

         chemin=pcChemin(0,n-1);
         flot+=t[2];

         cpt++;
         //cout<<cpt<<endl;
    }
    return flot;
}

int flotSortantGp(int s){
    int cpt=0;

    for(int i=0;i<Gp[s].size();i++){
        cpt+=Gp[s][i][1];

    }

    return cpt;

}
/*void copieChemin(int ind,int ind2,int w){
    chemin[ind2].resize(chemin[ind].size(),-1);
    for(int i=w+1;i<chemin[ind].size();i++)
        chemin[ind2][i]=chemin[ind][i];
}

void creationChemin(vector <int> pere[],int s,int ind,int w){
   if(pere[s][0]!=0){
         chemin[ind][w]=pere[s][0];
         creationChemin(pere,pere[s][0],ind,w-1);
         for(int i=1;i<pere[s].size();i++){
             chemin.push_back(vector < int >());
             copieChemin(ind,chemin.size()-1,w);
             chemin[chemin.size()-1][w]=pere[s][i];
             creationChemin(pere,pere[s][i],chemin.size()-1,w-1);
         }

   }
   else{

       chemin[ind][0]=0;

   }

}*/

void initGC(){
   // if(!Gc.empty()){
    for(int i=0;i<Gc.size();i++){

         for(int j=0;j<Gc[i].size();j++){


             Gc[i][j].clear();

        }

        Gc[i].clear();
    }

    Gc.clear();

   // }
        for(int i=0;i<n;i++){
        Gc.push_back(vector<vector<int> >());
        }


}

void ajouteAreteGc(int a, int b, int f, int c){

    Gc[a].push_back(vector<int>());
        Gc[a][Gc[a].size()-1].push_back(b);
        Gc[a][Gc[a].size()-1].push_back(f);
        Gc[a][Gc[a].size()-1].push_back(c);

}
bool existePas(int a,vector < int > v,int limite){
    bool b=true;
    int i=v.size()-1;
    while(b and i>limite){

        if(v[i]==a)b=false;
        else i--;
    }

    return b;
}
void creationGrapheCouche(vector< vector <int> >pere){
   // int s=1;
    int j=0;
    int indice;
    bool existe[n];
    for(int i=0;i<n;i++)existe[i]=false;
    vector < int > aTraiter=vector <int>();
    aTraiter.push_back(n-1);
    existe[n-1]=true;
    existe[0]=true;
    initGC();


        while(j<aTraiter.size()){

              if(pere[aTraiter[j]].empty()){j++;}
              else{
           for(int i=0;i<pere[aTraiter[j]].size();i++){

            //  if(existePas(pere[aTraiter[j]][i],aTraiter,aTraiter.size()-i-2)){
              if(!existe[pere[aTraiter[j]][i]]){    aTraiter.push_back(pere[aTraiter[j]][i]);existe[pere[aTraiter[j]][i]]=true;}
              
               indice=indiceAreteGp(pere[aTraiter[j]][i],aTraiter[j]);
               
               ajouteAreteGc(pere[aTraiter[j]][i],aTraiter[j],Gp[pere[aTraiter[j]][i]][indice][1],Gp[pere[aTraiter[j]][i]][indice][2]);


           }
            j++; }
        }


  


}


bool ensemblePCC(int s,int t){

    int cpt=0;
    int vu[n];//on met le rang où on le découvre puis on vérifie si le rang est égal sinon on le prend pas
    vector<vector <int> >pere=vector< vector<int> >()/*[2]*/;
    bool trouve=false;
    for( int i=0;i<n;i++){
        vu[i]=INT_MAX;
        pere.push_back(vector<int>());
    }
    vector<int> aTraiter=vector<int>();
    vu[0]=0;

    aTraiter.push_back(s);

    int j=0;
    int i=0;
//cout<<"aTraiter.size(): "<<aTraiter.size()<<endl;

    while(cpt<n && !trouve){//le chemin max est de taille n-1 dans le pire des cas

        //pour les nouveaux voisins, on regarde si c'est t sinon
        if(aTraiter.size()==j)cpt=n;
        else{ j=aTraiter.size();
                while(i<j){
//cout<<"aTraiter[i]: "<<aTraiter[i]<<endl;
                             //on parcours les nouveaux voisins du sommet courant et on met le sommet courant comme p�re
                             for(int k=0;k<Gp[aTraiter[i]].size();k++){
                                 
                                 if(vu[Gp[aTraiter[i]][k][0]]>=cpt/* && vu[Gp[aTraiter[i]][k][0]]>vu[aTraiter[i]]*/){
                                     //cout<<"Gp[aTraiter[i]][k][0]: "<<Gp[aTraiter[i]][k][0]<<" "<<cpt<<endl;
                                    
                                    if(Gp[aTraiter[i]][k][0]==t){//c'est gagn�

                                    trouve=true;

                                    pere[t].push_back(aTraiter[i]);
                                   // pere[t][1]=k;//G[aTraiter[i]][k][2]-G[aTraiter[i]][k][1];
                                    vu[Gp[aTraiter[i]][k][0]]=cpt;
                                    }
                                    else{

                                        pere[Gp[aTraiter[i]][k][0]].push_back(aTraiter[i]);
                                       // pere[Gp[aTraiter[i]][k][0]][1]=k;//G[aTraiter[i]][k][2]-G[aTraiter[i]][k][1];
                                        if(vu[Gp[aTraiter[i]][k][0]]!=cpt){
                                            aTraiter.push_back(Gp[aTraiter[i]][k][0]);
                                        vu[Gp[aTraiter[i]][k][0]]=cpt;
                                        }
                                    }
                                 }
                             }  

              i++;
            }
         
        }
        cpt++;
      
    }
   // for(int i=0;i<aTraiter.size();i++)cout<<aTraiter[i]<<" ";
   // cout<<endl;
    //for(int i=0;i<n;i++){cout<<i<<" : ";
    //    for(int j=0;j<pere[i].size();j++){cout<<pere[i][j]<<" ";}
    //    cout<<endl;}
    //afficheGraphe(Gp);*/
    if(trouve)creationGrapheCouche(pere);
    return trouve;
}
int Min(int a , int b){

    if(a<b)return a;else return b;

}



int flotGc(int s,int min){
   //version glouton, poussons comme des boeuf et si ca passe plus on réduit derriere


    if(s==n-1)return min;
    else{int max=0;int tp=0;
    int i=0;
    while(i<Gc[s].size() and min>0){//on parcours tout les voisins de s

        tp=flotGc(Gc[s][i][0],Min(/*Gc[s][i][2]-*/Gc[s][i][1],min));
        max+=tp;
        min-=tp;//min représente ce qui reste a donner
        //augmenter(Gc[s][i][0],tp);
      //  Gc[s][i][1]+=tp;
        Gc[s][i][1]-=tp;
    
        i++;

    }
    return max;


    }
}

void supprimeArete(int a ,int b){

    if(b!=G[a].size()-1){
        ind[a][G[a][b][0]]=-1;
        G[a][b][0]=G[a][G[a].size()-1][0];
        G[a][b][1]=G[a][G[a].size()-1][1];
        G[a][b][2]=G[a][G[a].size()-1][2];
        ind[a][G[a][b][0]]=b;
    }
    G[a][G[a].size()-1].clear();
    G[a].pop_back();

}
void supprimeAreteGp(int a ,int b){

    if(b!=Gp[a].size()-1){
        indgp[a][Gp[a][b][0]]=-1;
        Gp[a][b][0]=Gp[a][Gp[a].size()-1][0];
        Gp[a][b][1]=Gp[a][Gp[a].size()-1][1];
        Gp[a][b][2]=Gp[a][Gp[a].size()-1][2];
        indgp[a][Gp[a][b][0]]=b;
    }
    Gp[a][Gp[a].size()-1].clear();
    Gp[a].pop_back();

}

void MajFlotGc(){

   /* vector <int> aTraiter;
    aTraiter.push_back(0);
    bool vu[n];
    for(int i=0;i<n;i++)vu[i]=false;
    vu[0]=true;*/
    int indice;
  /*  int j=0;
    int s=1;
    
    while(j<s){

           for(int i=0;i<Gc[aTraiter[j]].size();i++){
               
              if(!vu[Gc[aTraiter[j]][i][0]]){ aTraiter.push_back(Gc[aTraiter[j]][i][0]);vu[Gc[aTraiter[j]][i][0]]=true;}
      
               indice=indiceAreteGp(aTraiter[j],Gc[aTraiter[j]][i][0]);
               Gp[aTraiter[j]][indice][1]=Gc[aTraiter[j]][i][1];
               if(Gp[aTraiter[j]][indice][1]==Gp[aTraiter[j]][indice][2]){//suppression, donc on va échanger avec le dernier vector et penser a changer l'indice
                cout<<"0"<<endl;
                   indice=indiceAreteGp(Gc[aTraiter[j]][i][0],aTraiter[j]); 
                   if(indice!=-1)supprimeAreteGp(Gc[aTraiter[j]][i][0],indice);
               }
                   else{  
             cout<<"1"<<endl;
                   if(Gp[aTraiter[j]][indice][1]==0)supprimeAreteGp(aTraiter[j],indice);
                     cout<<"2"<<endl;
                        indice=indiceAreteGp(Gc[aTraiter[j]][i][0],aTraiter[j]);cout<<"2.1"<<endl;
                        if(indice==-1)ajouteAreteGp(Gc[aTraiter[j]][i][0],aTraiter[j],Gc[aTraiter[j]][i][2]-Gc[aTraiter[j]][i][1],Gc[aTraiter[j]][i][2]); 
                        else{ cout<<"3"<<endl;
                            Gp[Gc[aTraiter[j]][i][0]][indice][1]=Gc[aTraiter[j]][i][2]-Gc[aTraiter[j]][i][1];

                        }
                   }
               }

           

             s=aTraiter.size();j++;
           
    }*/

    for(int i=0;i<n;i++){
    
        for(int j=0;j<Gc[i].size();j++){
           
            indice=indiceAreteGp(i,Gc[i][j][0]);
          //  cout<<i<<"->"<<Gc[i][j][0]<<endl;
         //   cout<<"indice: "<<indice<<endl;
            Gp[i][indice][1]=Gc[i][j][1];
           
            if(Gp[i][indice][1]==Gp[i][indice][2]){ 
                
                indice=indiceAreteGp(Gc[i][j][0],i);
               
                if(indice!=-1)supprimeAreteGp(Gc[i][j][0],indice);
               
            }
            else{  
                 if(Gp[i][indice][1]==0)supprimeAreteGp(i,indice);
             
                 indice=indiceAreteGp(Gc[i][j][0],i);
                        if(indice==-1)ajouteAreteGp(Gc[i][j][0],i,Gc[i][j][2]-Gc[i][j][1],Gc[i][j][2]); 
                        else{ 
                            Gp[Gc[i][j][0]][indice][1]=Gc[i][j][2]-Gc[i][j][1];

                        }
                
            }
        } 
    }
} 


int Dinic(){
   
    int f=0;
    
    graphEcart();
    bool b=ensemblePCC(0,n-1);
   
    while(b){
     
        f+=flotGc(0,INT_MAX);
       
        MajFlotGc();
       
        
        b= ensemblePCC(0,n-1);
        //cout<<f<<endl;
         
     
    }
    return f;
}



vector <int> chaineAmeliorante(){
   
   vector <int> aTraiter=vector<int>();
   aTraiter.push_back(0);
   int j=0;
  
   bool trouve=false;
   int vu[n];
   for(int i=0;i<n;i++)vu[i]=-1;
   vu[0]=-2;
   int i=0;  
       
   while(j<aTraiter.size() && !trouve){
       
       //successeur
       i=0;

       while(i<G[aTraiter[j]].size() && !trouve){
           if((vu[G[aTraiter[j]][i][0]]==-1) && (G[aTraiter[j]][i][2]>G[aTraiter[j]][i][1] )){
               vu[G[aTraiter[j]][i][0]]=aTraiter[j];
                if(G[aTraiter[j]][i][0] ==n-1)trouve=true;
                else aTraiter.push_back(G[aTraiter[j]][i][0]);
               
           }
           i++;
       }
  
       //predecesseur
       i=1;
       while(i<n-1 && !trouve){
           if(ind[i][aTraiter[j]]!=-1){
              if((vu[i]==-1) && (G[i][ind[i][aTraiter[j]]][1]>0)){
                  vu[i]=aTraiter[j];
                  //vu[G[i][ind[i][aTraiter[j]]][0]]=aTraiter[j];
                 /* if(i==n-1)trouve=true;
                  else*/ aTraiter.push_back(i);
              } 
           }
           i++;
       }
     j++;  
   }
   //creation chaine
   vector<int> chaine=vector<int>();

   if(trouve){
       vector<int> chainetp=vector<int>();
 
        chainetp.push_back(n-1);
  
        i=0;
       
        
       while(trouve){
           
           chainetp.push_back(vu[chainetp[i]]);
           if(vu[chainetp[i]]==0)trouve=false;
           else i++;
       }
  
       
       for(int k=chainetp.size()-1;k>-1;k--){
           
           chaine.push_back(chainetp[k]);
           
       }
        
   }
   else{
       
       chaine.push_back(-1);
       
   }
  
   return chaine;
}

int fordFulkerson(){
    
    int f=0;
    vector<int> chaine=vector<int>();
    chaine=chaineAmeliorante();
    //cout<<"a"<<endl;
    int min=0;
    int mintp=0;
    int tp=0;
    while(chaine[0]!=-1){
 // cout<<"b"<<endl;
        //calcul plus petit arc

        if(ind[chaine[0]][chaine[1]]==-1){//cout<<"c"<<endl;
            tp=ind[chaine[1]][chaine[0]];
            min=G[chaine[1]][tp][1];//cout<<"b : "<<min<<endl;
        }else{//cout<<"d"<<endl;
            tp=ind[chaine[0]][chaine[1]];
            min=G[chaine[0]][tp][2]-G[chaine[0]][tp][1];//cout<<"a : "<<min<<endl;
        }
   mintp=min;
        for(int i=1;i<chaine.size()-1;i++){
           //cout<<"e"<<endl;
            tp=ind[chaine[i]][chaine[i+1]];
            if(tp==-1){//cout<<"f"<<endl;
                //tp=ind[chaine[i]][chaine[i+1]];
                  tp=ind[chaine[i+1]][chaine[i]];
                mintp=G[chaine[i+1]][tp][1];//cout<<"b1 : "<<mintp<<endl;
               
            }else{//cout<<"g"<<endl;
               mintp=G[chaine[i]][tp][2]-G[chaine[i]][tp][1];//cout<<"a1 : "<<mintp<<endl;
             
            }

                if(mintp<min){//cout<<"h"<<endl;
                    min=mintp;
                }
        }
        //fin calcul plus petit arc
        
        //debut augmentation et diminution
        f+=min;//cout<<min<<endl;
 //cout<<"i"<<endl;
        for(int i=0;i<chaine.size()-1;i++){
            
            if(ind[chaine[i]][chaine[i+1]]==-1){ //cout<<"j"<<endl;
                tp=ind[chaine[i+1]][chaine[i]];
                G[chaine[i+1]][tp][1]-=min;
            }else{ //cout<<"k"<<endl;
                tp=ind[chaine[i]][chaine[i+1]];
                G[chaine[i]][tp][1]+=min;
            }
            
        }
 //cout<<"l"<<endl;
        chaine.clear();
        //afficheGraphe(G);
      chaine=chaineAmeliorante();  
 
    }  
    return f;
}

void ajouteListeAretes(int a, int b, int c){
      
     aretes.push_back(vector<int>());
     aretes[aretes.size()-1].push_back(a);
     aretes[aretes.size()-1].push_back(b);
     aretes[aretes.size()-1].push_back(c);
}

 
    

int capaMax(){
   
    for(int i=0;i<n;i++){   
        for(int j=0;j<G[i].size();j++){
            //if(G[i][j][3]>max)max=G[i][j][3]; 
            ajouteListeAretes(i,G[i][j][0],G[i][j][2]);
            
        }    
    }
    sort (aretes.begin(), aretes.end(),MonFoncteur());
    //trierAretes();
    
    return aretes[aretes.size()-1][2];
    
}

int grapheEcart2(int min,int indDebut){//retourne l'indice d'ou on doit commencer pour le prochain Ge
    int i=indDebut;

    while(i>-1 && aretes[i][2]>=min){
     
        ajouteAreteGp(aretes[i][0],aretes[i][1],aretes[i][2],aretes[i][2]);
  
        i--;
    }
    return i;
}

int capacityScaling(){
    //aretes=new vector<int[3]>();
    double c=2 * log(capaMax());

    int f=0;int c2=0;
    vector<int> chemin;
    for(int i=0;i<n;i++){
        Gp.push_back(vector<vector<int> >());
    }
 
    int indDebut=aretes.size()-1;
    while(c>=1 && indDebut>-1){
      
       indDebut= grapheEcart2((int)c,indDebut);
    
       chemin=pcChemin(0,n-1);
  
    
       while(chemin[0]!=-1){
          c2=plusPetitArc(chemin)[2];
 
          f+=c2;
          MaJGp(chemin,c2);
  
          chemin=pcChemin(0,n-1);
    
        }
        c=c/2;
  
      
    }
 
    return f;
}

/*
 *
 */
int main(int argc, char** argv) {

/*cout<<" *********** Debut initialisation G : **************"<<endl;
initGraphe();
afficheGraphe(G);
cout<<" *********** Debut Creation Graphe d'ecart Gp **************"<<endl;
graphEcart();
afficheGraphe(Gp);
cout<<" *********** Debut pcC G : **************"<<endl;
pcChemin(0, n-1);
*/
    m=0;




    //initGraphe();

// initGrapheRandom(10,20,50);
 //   afficheGraphe(G);
    
    
    
  //  graphEcart();
    /*
    afficheGraphe(Gp);
    vector<int> chemin=pcChemin(0, n-1);
    if(chemin[0]!=-1){

    for(int l=0;l<chemin.size();l++)cout<< chemin[l]<<" ";
    cout<<endl;
    if(chemin.size()>1){
    int *t=plusPetitArc(chemin);
    cout<< "plus petit arc: " <<t[0]<<" "<<t[1]<<" de valeur:" <<t[2]<<endl;
   MaJGp(chemin,t[2]);

    }
    }
    else{

      cout<< "chemin de longueur: 0"<<endl;


    }*/

    /*cout<<"flot Max: "<<GpFinal()<<endl;
      cout<<"flot sortant de p: "<<flotSortantGp(n-1)<<endl;*/

   /* vector < vector < vector < int > > > chemin=ensemblePCC(0, n-1);
    if(chemin[0][0][0]!=-1){


    }*/

  /*  ensemblePCC(0,n-1);
    cout<<"a"<<endl;
    afficheGraphe(Gc);
    flotGc(0,INT_MAX);
    cout<<"b"<<endl;
    MajFlotGc();
    afficheGraphe(Gc);
    cout<<"c"<<endl;*/

   //Dinic();
   // cout<<"flot augmente de " <<fordFulkerson()<<endl;
  //   afficheGraphe(G);
    
  //  cout<<capacityScaling()<<endl;
  //   afficheGraphe(Gp);
   

    
    /*et c'est parti pour les test*/
  
    
    n=2000;
  //initGrapheRandom(10,25,25);
   //afficheGraphe(G);
    initGrapheRandom(10,40,40);
  
    //Edmond-karp
  /*   graphEcart();
   
    GpFinal();
    cout<<flotSortantGp(n-1)<<endl;*/
  
    
    //dinic
    

    
   // cout<<Dinic()<<endl;
   
    //ford fulkerson
    //cout<<fordFulkerson()<<endl;
    
   
   //capacity scaling
    cout<<capacityScaling()<<endl;
   
  //   cout<<m<<endl;
         return 0;
}
